/*-
 * Copyright 2012 Guram Dukashvili
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
//---------------------------------------------------------------------------
#include "sys.h"
#include "array.h"
//---------------------------------------------------------------------------
#define AR_STATIC_DATA(ar) ((uint8_t *) (ar) + sizeof(array))
//---------------------------------------------------------------------------
array * array_new(void)
{
  array * ar = salloc(sizeof(array),NULL);
  if( ar != NULL )
    array_init(ar);
  return ar;
}
//---------------------------------------------------------------------------
void array_init(array * ar)
{
  ar->a = NULL;
  ar->count = 0;
  ar->reserve = 16;
  ar->reserved = 0;
  ar->element_size = 0;
  ar->resize_count = ar->copy_count = 0;
  ar->element_init = ar->element_destroy = NULL;
  ar->element_copy = NULL;
  ar->element_compare = NULL;
  ar->element_xchg = NULL;
  ar->object = NULL;
}
//---------------------------------------------------------------------------
void array_init_from(array * ar,const array * src,uintptr_t static_data_size)
{
  ar->a = NULL;
  ar->count = 0;
  ar->reserve = src->reserve;
  ar->element_size = src->element_size;
  ar->reserved = (ar->static_data_size = static_data_size) / ar->element_size;
  ar->resize_count = ar->copy_count = 0;
  ar->element_init = src->element_init;
  ar->element_destroy = src->element_destroy;
  ar->element_copy = src->element_copy;
  ar->element_compare = src->element_compare;
  ar->element_xchg = src->element_xchg;
  ar->object = src->object;
}
//---------------------------------------------------------------------------
void array_init_copy(array * ar,const array * src,uintptr_t static_data_size)
{
  array_init_from(ar,src,static_data_size);
  array_copy(ar,src);
}
//---------------------------------------------------------------------------
void array_destroy(array * ar)
{
  if( ar->element_destroy != NULL ){

    uint8_t * data = ar->a + ar->count * ar->element_size;

    while( data > ar->a ){
      data -= ar->element_size;
      ar->element_destroyf(data,ar->object);
    }
  }

  if( ar->a != AR_STATIC_DATA(ar) )
    sfree(ar->a);
}
//---------------------------------------------------------------------------
void array_delete(array * ar)
{
  array_destroy(ar);
  sfree(ar);
}
//---------------------------------------------------------------------------
void array_copy(array * ar,const array * src)
{
  array_resize(ar,src->count);

  if( ar->element_copy != NULL ){

    uintptr_t i, e = ar->count;
    uint8_t * p = ar->a, * a = src->a;

    for( i = 0; i < e; i++, p += ar->element_size, a += src->element_size )
      ar->element_copyf(p,a,ar->object);
  }
  else {
#if COMPILE_RUNTIME_CHECKS
    if( ar->element_size != src->element_size ){
      fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
      abort();
    }
#endif
    memcpy(ar->a,src->a,ar->count * ar->element_size);
  }
}
//---------------------------------------------------------------------------
void array_set_element_size(array * ar,uintptr_t element_size,uintptr_t static_data_size)
{
#if COMPILE_RUNTIME_CHECKS
  if( ar->count != 0 ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif
  ar->element_size = element_size;
  ar->reserve = element_size > 4096 ? 1 : 4096 / element_size;
  ar->reserved = (ar->static_data_size = static_data_size) / element_size;
}
//---------------------------------------------------------------------------
void array_resize(array * ar,uintptr_t n)
{
  uint8_t * a, * p1, * p2;

  if( n != ar->count ){
    errno = 0;

    if( n > ar->static_data_size / ar->element_size ){
      if( n > ar->reserved - ar->reserve && n <= ar->reserved ){
        a = ar->a;
      }
      else {
        uint32_t golden_selection_size = n * 5;
        golden_selection_size /= 8;

        if( ar->reserve == 0 ) ar->reserve = golden_selection_size + 1;

        if( ar->copy_count > ar->resize_count )
          ar->reserve <<= 1;
        else if( ar->copy_count < ar->resize_count )
          ar->reserve >>= 1;

        if( ar->reserve > golden_selection_size && golden_selection_size > 0 )
          ar->reserve = golden_selection_size;

        a = salloc(ar->element_size * (n + ar->reserve),NULL);
        if( a == NULL ){
          if( n > ar->count ) return;
          a = ar->a;
          errno = 0;
        }
        ar->reserved = n + ar->reserve;
      }
    }
    else {
      a = ar->static_data_size > 0 ? AR_STATIC_DATA(ar) : NULL;
      ar->reserved = ar->static_data_size / ar->element_size;
    }

    if( a != ar->a ){

      uintptr_t i, e = ar->count > n ? n : ar->count;

      if( ar->element_init != NULL ){
        p1 = a;
        p2 = p1 + n * ar->element_size;
        while( p1 < p2 ){
          ar->element_initf(p1,ar->object);
          p1 += ar->element_size;
        }
      }

      if( ar->element_copy != NULL ){
        p1 = a;
        p2 = ar->a;
        for( i = 0; i < e; i++, p1 += ar->element_size, p2 += ar->element_size )
          ar->element_copyf(p1,p2,ar->object);
      }
      else
        memcpy(a,ar->a,e * ar->element_size);

      ar->copy_count += e;

      if( ar->element_destroy != NULL ){
        p1 = ar->a;
        p2 = p1 + ar->count * ar->element_size;
        while( p1 < p2 ){
          ar->element_destroyf(p1,ar->object);
          p1 += ar->element_size;
        }
      }

      if( ar->a != AR_STATIC_DATA(ar) && a != ar->a )
        sfree(ar->a);

      ar->a = a;
    }
    else {
      if( ar->element_init != NULL ){
        p1 = ar->a + ar->count * ar->element_size;
        p2 = ar->a + n * ar->element_size;
        while( p1 < p2 ){
          ar->element_initf(p1,ar->object);
          p1 += ar->element_size;
          ar->count++;
        }
      }

      if( ar->element_destroy != NULL ){
        p1 = ar->a + ar->count * ar->element_size;
        p2 = ar->a + n * ar->element_size;
        while( ar->count > n ){
          ar->count--;
          p1 -= ar->element_size;
          ar->element_destroyf(p1,ar->object);
        }
      }
    }
    ar->count = n;
    ar->resize_count++;

    if( (ar->resize_count & 0xFFFFF) == 0 )
      ar->resize_count = ar->copy_count = 0;
  }
}
//---------------------------------------------------------------------------
void array_append(array * ar)
{
  array_resize(ar,ar->count + 1);
}
//---------------------------------------------------------------------------
void array_append_copy(array * ar,const void * data)
{
  array_resize(ar,ar->count + 1);

  if( errno == 0 ){

    void * p = ar->a + (ar->count - 1) * ar->element_size;

    if( ar->element_copy != NULL )
      ar->element_copyf(p,data,ar->object);
    else
      memcpy(p,data,ar->element_size);

  }
}
//---------------------------------------------------------------------------
void array_insert(array * ar,uintptr_t idx)
{
  array_insert_copy(ar,idx,NULL);
}
//---------------------------------------------------------------------------
void array_insert_copy(array * ar,uintptr_t idx,const void * data)
{
#if COMPILE_RUNTIME_CHECKS
  if( idx > ar->count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif

  array_resize(ar,ar->count + 1);

  if( errno == 0 ){

    uint8_t * p = ar->a + idx * ar->element_size;

    if( ar->element_copy != NULL ){
      uint8_t * a = ar->a + (ar->count - 1) * ar->element_size;
      uintptr_t i;

      for( i = ar->count - 1; i > idx; i--, a -= ar->element_size )
        ar->element_copyf(a,a - ar->element_size,ar->object);

    }
    else {
      memmove(p + ar->element_size,p,(ar->count - 1 - idx) * ar->element_size);
    }

    if( data != NULL ){
      if( ar->element_copy != NULL )
        ar->element_copyf(p,data,ar->object);
      else
        memcpy(p,data,ar->element_size);
    }
  }
}
//---------------------------------------------------------------------------
void array_remove(array * ar,uintptr_t idx)
{
  uint8_t * p = ar->a + idx * ar->element_size;

#if COMPILE_RUNTIME_CHECKS
  if( idx >= ar->count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif

  if( ar->element_copy != NULL ){
    uintptr_t i;

    for( i = idx + 1; i < ar->count; i++, p += ar->element_size )
      ar->element_copyf(p,p + ar->element_size,ar->object);
  }
  else {
    memcpy(p,p + ar->element_size,(ar->count - idx - 1) * ar->element_size);
  }

  array_resize(ar,ar->count - 1);
}
//---------------------------------------------------------------------------
void array_copy_paste(
  array * ar,
  uintptr_t dst_position,
  const array * src,
  uintptr_t src_position,
  uintptr_t count)
{
#if COMPILE_RUNTIME_CHECKS
  if( dst_position > ar->count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
  if( src_position >= src->count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
  if( src_position + count > src->count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif

  array_resize(ar,ar->count + count);

  if( errno == 0 ){

    uint8_t * p = ar->a + dst_position * ar->element_size;
    uint8_t * a = ar->a + (ar->count - 1) * ar->element_size;
    uintptr_t i, s = count * ar->element_size;

    if( ar->element_copy != NULL ){

      for( i = ar->count - 1; i > dst_position + count; i--, a -= ar->element_size ){
        uint8_t * a = ar->a + i * ar->element_size;
        ar->element_copyf(a,a - s,ar->object);
      }

      a = src->a + src_position * src->element_size;

      for( i = 0; i < count; i++, p += ar->element_size, a += src->element_size )
        ar->element_copyf(p,a,ar->object);
    }
    else {
#if COMPILE_RUNTIME_CHECKS
      if( ar->element_size != src->element_size ){
        fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
        abort();
      }
#endif
      memmove(p + s,p,s);
      memcpy(p,src->a + src_position * src->element_size,count * src->element_size);
    }

  }
}
//---------------------------------------------------------------------------
intptr_t array_lookup(const array * ar,const void * data,uintptr_t * insert_position)
{
  intptr_t low = 0, high = ar->count - 1, pos, c;

  *insert_position = 0;

  if( ar->element_compare != NULL )
    return array_lookupf(ar,data,insert_position,ar->element_comparef);

  for(;;){

    pos = (low + high) / 2;

    if( low > high ) break;

    c = memcmp(data,ar->a + pos * ar->element_size,ar->element_size);

    if( c > 0 ){
      *insert_position = low = pos + 1;
    }
    else if( c < 0 ){
      high = (*insert_position = pos) - 1;
    }
    else {
      errno = EEXIST;
      return pos;
    }
  }

  errno = ENOENT;
  return -1;
}
//---------------------------------------------------------------------------
intptr_t array_lookupf(const array * ar,const void * data,uintptr_t * insert_position,void * element_comparef)
{
  intptr_t low = 0, high = ar->count - 1, pos, c;

  *insert_position = 0;

  for(;;){

    pos = (low + high) / 2;

    if( low > high ) break;

    c = (*(intptr_t (*)(const void *,const void *,...))
      element_comparef)(data,ar->a + pos * ar->element_size,ar->object);

    if( c > 0 ){
      *insert_position = low = pos + 1;
    }
    else if( c < 0 ){
      high = (*insert_position = pos) - 1;
    }
    else {
      errno = EEXIST;
      return pos;
    }
  }

  errno = ENOENT;
  return -1;
}
//---------------------------------------------------------------------------
intptr_t array_lookup_insert_copy(array * ar,const void * data)
{
  uintptr_t insert_position;
  intptr_t i = array_lookup(ar,data,&insert_position);
  if( i < 0 )
    array_insert_copy(ar,insert_position,data);
  return i;
}
//---------------------------------------------------------------------------
static __inline__ intptr_t compare(const array * ar,intptr_t p1,intptr_t p2)
{
  return ar->element_compare != NULL
    ? ar->element_comparef(ar->a + p1 * ar->element_size,ar->a + p2 * ar->element_size,ar->object)
    : memcmp(ar->a + p1 * ar->element_size,ar->a + p2 * ar->element_size,ar->element_size);

}
//---------------------------------------------------------------------------
static __inline__ void xchg(const array * ar,void * x,intptr_t x1,intptr_t x2)
{
  void * px1 = ar->a + x1 * ar->element_size;
  void * px2 = ar->a + x2 * ar->element_size;

  if( ar->element_xchg != NULL ){
    ar->element_xchgf(px1,px2,x,ar->object);
  }
  else if( ar->element_copy != NULL ){
    ar->element_copyf(x,px1,ar->object);
    ar->element_copyf(px1,px2,ar->object);
    ar->element_copyf(px2,x,ar->object);
  }
  else {
    memxchg(px1,px2,ar->element_size);
  }
}
//---------------------------------------------------------------------------
static void my_qsort(const array * ar,void * x,intptr_t lb,intptr_t ub)
{
  intptr_t l, r, m;

  if( lb < ub ){

    if( ub - lb < 12 ){

      for( r = ub; r > lb; r-- ){

        for( m = r, l = m - 1; l >= lb; l-- )
          if( compare(ar,m,l) < 0 ) m = l;

        xchg(ar,x,m,r);
      }

    }
    else {

      m = lb + ((ub - lb) >> 1);
      l = lb, r = ub;

      for(;;){

        while( l < r && compare(ar,m,l) > 0 ) l++;
        while( r >= l && compare(ar,m,r) < 0 ) r--;

        if( l >= r ) break;

        xchg(ar,x,l,r);

        if( r == m ) m = l;
        else if( l == m ) m = r;

        l++;
        r--;
      }

      my_qsort(ar,x,lb,r);
      my_qsort(ar,x,r + 1,ub);

    }
  }
}
//---------------------------------------------------------------------------
void array_sort(array * ar)
{
  void * x = NULL;

  if( ar->element_xchg != NULL || ar->element_copy != NULL ){
    x = ar->element_size <= 2048 ? alloca(ar->element_size) : salloc(ar->element_size,NULL);
    if( x == NULL ) return;
  }

  if( ar->element_init != NULL )
    ar->element_initf(x,ar->object);

  my_qsort(ar,x,0,ar->count - 1);

  if( ar->element_destroy != NULL )
    ar->element_destroyf(x,ar->object);

  if( ar->element_size > 2048 ) sfree(x);
}
//---------------------------------------------------------------------------
void array_shuffle(array * ar,struct rand * rnd,uintptr_t count)
{
  void * x = NULL;

  if( ar->element_xchg != NULL || ar->element_copy != NULL ){
    x = ar->element_size <= 2048 ? alloca(ar->element_size) : salloc(ar->element_size,NULL);
    if( x == NULL ) return;
  }

  if( ar->element_init != NULL )
    ar->element_initf(x,ar->object);

  while( count > 0 ){
    xchg(ar,x,rand_next(rnd) % ar->count,rand_next(rnd) % ar->count);
    count--;
  }

  if( ar->element_destroy != NULL )
    ar->element_destroyf(x,ar->object);

  if( ar->element_size > 2048 ) sfree(x);
}
//---------------------------------------------------------------------------
